package com.clstu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 写一个根据 逆波兰表达式 算出结果的例子
 * ----(进化版)---->根据中缀表达式直接转换成后最表达式并计算结果(可以计算带括号的算式和多位数)
 *
 */
public class PolandNotation {
    public static void main(String[] args) {
        //1.将一个中缀表达式转换成后缀表达式
        //定义一个中缀表达式
        String expression = "1+2+  8.5 * (6+50) /2 *(4+13)";
        //为了方便遍历,将其各个符号或数字存入ArrayList中
        List<String> exp = toArrayListPlus(expression);
        //查看exp
        System.out.println(exp);
        //中缀转后缀的过程:(非常重要,面试可能会问)
        //1.定义s1和s2两个栈,依次遍历表达式中的各个字符或数字,
        // 如果是数字,直接入s2
        // 如果是(直接入栈s1
        // 如果是运算符且栈空,直接入栈 s1
        // 如果是运算符栈不空,比较跟栈顶的优先级,如果优先级更大,入栈s1,否则,s1.pop()-->s2.push(),再接着反复比较跟栈顶的优先级
        // 如果是),则 s1.pop()--->s2.push(), 直到弹出一个(为止 ,
        // (注意,此时弹出的"("和扫描到的")"都不入栈,直接不管,即消除了一对括号)
        //最后:表达式扫描完毕后 循环s1.pop()--->s2.push()直到s1栈空(最后s2中就是中缀表达式
        //遍历扫描中缀表达式
        //定义两个栈,(因为上面的过程最后s2是栈结构,表达式不方便正向遍历,于是s2在这里用ArrayList代替)
        Stack<String> s1 = new Stack<>();
        ArrayList<String> s2 = new ArrayList<>();
        for (String str : exp) {
            //如果是数字
            if (str.matches("[1-9]\\d*(\\.\\d+)?")){
                s2.add(str);
            }else if(str.equals("(")){//如果是左括号(
                s1.push(str);
            }else if(str.equals(")")){//如果是右括号)
                //遍历取出s1中的符号
                while (true){
                    String s = s1.pop();
                    //如果是(
                    if(s.equals("(")){
                        break;
                    }
                    //压入s2
                    s2.add(s);
                }
            }else {//如果是运算符
                //循环比较跟栈顶的优先级
                while (true) {
                    //如果s1空
                    if(s1.isEmpty()){
                        s1.push(str);
                        break;
                    }
                    //如果栈顶是(
                    if (s1.peek().equals("(")){
                        s1.push(str);
                        break;
                    }
                    //如果优先级大于栈顶
                    if (priority(str) > priority(s1.peek())) {
                        s1.push(str);
                        break;
                    }
                    //如果都不是:s1.pop--->s2.push
                    s2.add(s1.pop());
                }
            }
        }
        //将s1中剩余的所有运算符依次s1.pop() ----> s2.push()
        while (!s1.isEmpty()){
            s2.add(s1.pop());
        }
        //查看s2
        System.out.println(s2);
        //循环结束,s2中存放的就是该中缀表达式对应的逆波兰表达式
        //定义一个逆波兰表达式 它的中缀表达式:(30+4)*5-6 , 4*5-8+60+8/2=76
        //为了演示方便,先将数字和字符都用空格隔开
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";//逆波兰表达式(后缀表达式)
        //思路:为了遍历字符串方便,先将各个数字或字符放入ArrayList中,然后遍历ArrayList,栈就利用java的Stack就行了
        //2.逆波兰表达式计算过程(重要)
        //                :依次遍历各个字符, 如果是数字,入栈, 如果是运算符,弹出两个数跟这个运算符做运算,再将结果入栈,
        //                 遍历结束栈中留下的就是表达式的运算结果
        //得到对应的ArrayList
        List<String> sfExpList = toArrayList(suffixExpression);
        //遍历集合,运算,得到结果
        //创建Stack
        Stack<Double> stack = new Stack<>();
        //创建辅助变量(两个操作数和一个结果)
        double n1 = 0;
        double n2 = 0;
        double res = 0;
        for (String str : s2) {
            //如果是数字
            if(str.matches("[1-9]\\d*(\\.\\d+)?")){
                stack.push(Double.parseDouble(str));
            }else {//否则就是运算符
                n2 = stack.pop();//注意先n2接受,栈后进先出的原则
                n1 = stack.pop();
                res = cal(n1,n2,str);
                stack.push(res);
            }
        }
        //打印结果
        System.out.println(expression+" = "+stack.pop());

    }

    //编写方法根据表达式返回存入各个字符后的ArrayList
    public static List<String> toArrayList(String expression){
        //创建ArrayList
        ArrayList<String> res = new ArrayList<>();
        //分割表达式
        String[] s = expression.split(" ");
        //遍历存入
        for (String regStr : s) {
            res.add(regStr);
        }
        return res;
    }

    //编写方法根据传入的中缀表达式转换成存入各个字符或数字后的Arraylist
    public static List<String> toArrayListPlus(String expression){
        //创建arrayList
        List<String> arrayList = new ArrayList<>();
        //遍历扫描整个表达式,分别存入数据
        //可以利用正则表达式
        //定义正则表达式(正则表达式支持表达式有空格,空格被过滤掉了)
        String regStr = "[1-9]\\d*(\\.\\d+)*|\\+|-|\\*|/|\\(|\\)";//注意写正则表达式的时候.需要转义\\.
        Pattern pattern = Pattern.compile(regStr);
        Matcher matcher = pattern.matcher(expression);
        while (matcher.find()){
            arrayList.add(matcher.group(0));
        }
        return arrayList;
    }

    //编写方法根据 n1 n2 op ,得到结果
    public static double cal(double n1,double n2,String op){
        switch (op){
            case "+":
                return n1+n2;
            case "-":
                return n1-n2;
            case "*":
                return n1*n2;
            case "/":
                return n1/n2;
            default:
                throw new RuntimeException("运算符不正确,失败");
        }
    }

    //编写方法返回运算符的优先级,数字约大优先级越高
    public static int priority(String s){
        switch (s){
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            default:
                System.out.println(s);
                throw new RuntimeException(s+"该运算符暂时不做处理,失败");
        }
    }
}
